package com.tgy.dynamic.programming;

/**
 * @Author: tgy
 * @Date: 2020/11/6 9:43 下午
 */
public class MoneyChange {

    private int[]changes = {1,5,20,25};

    public int changeMoney(int money) {

        int[] cache = new int[money + 1];
        int[] curMoney = new int[cache.length];
        for (int change : changes) {

            cache[change] = 1;
            curMoney[change] = change;
        }

        for (int i = 1; i <= money; i++) {

            if (cache[i] != 0) {

                continue;
            }

            int min = Integer.MAX_VALUE;
            int cMoney = 0;
            for (int change : changes) {

                if (i > change) {

                    if (min > cache[i - change]) {

                        min = cache[i - change];
                        cMoney = change;
                    }
                }
            }

            cache[i] = min + 1;
            curMoney[i] = cMoney;
        }

        for (int i = 1; i <= money; i++) {

            printMoneny(i,curMoney);
        }

        return cache[money];
    }

    public int changeMoney02(int money) {

        int[] cache = new int[money + 1];
        int[] curMoney = new int[cache.length];
        for (int change : changes) {

            if (change > money) {

                continue;
            }
            cache[change] = 1;
            curMoney[change] = change;
        }

        changeMonenyIn(money,cache,curMoney);
        for (int i = 1; i <= money; i++) {

            printMoneny(i,curMoney);
        }

        return cache[money];
    }

    private void printMoneny(int money,int[] curMoney) {


        StringBuilder sb = new StringBuilder(String.valueOf(money));
        sb.append(" 组合: ");
        int cMoney;
        while (true) {

            cMoney = curMoney[money];
            sb.append(cMoney).append(",");
            money = money - cMoney;

            if (money <= 0) {

                break;
            }
        }

        if (sb.charAt(sb.length() - 1) == ',') {

            sb.deleteCharAt(sb.length() - 1);
        }

        System.out.println(sb);
    }

    private int changeMonenyIn(int money, int[]cache, int[] curMoney) {

        if (cache[money] == 0) {

            int min = Integer.MAX_VALUE;
            int lastMoney = 0;
            for (int change : changes) {

                if (money > change ) {
                    int nextMoney = changeMonenyIn(money-change,cache,curMoney);

                    if (min > nextMoney) {

                        min = nextMoney;
                        lastMoney = change;
                    }
                }
            }
            curMoney[money] = lastMoney;
            cache[money] = min + 1;
        }
        return cache[money];
    }

    public int changeMoney01(int money) {


        int min = Integer.MAX_VALUE;
        for (int change : changes) {

            if (change == money) {

                return 1;
            }

            if (money  > change) {
                // 进来了就选择了对应的值
                min = Math.min(min,changeMoney(money - change));
            }
        }

        return min + 1;
    }



}
